观察样例可以发现：
-
当 时，不能覆盖所有点。（恰好覆盖 的图）
-
和 是同一种方案。
所以答案为
#include <cstdio>
int Phi( int x ) {
int Ans = x;
for( int i = 2 ; 1ll * i * i <= x ; i ++ )
if( x % i == 0 ) {
Ans = Ans / i * ( i - 1 );
while( x % i == 0 ) x /= i;
}
if( x > 1 ) Ans = Ans / x * ( x - 1 );
return Ans;
}
int n;
int main( ) {
while( ~scanf("%d",&n) )
printf("%d\n", Phi( n ) / 2 );
return 0;
}
